#include<string>
#include<algorithm>
using namespace std;
class Solution {
public:
    int getMoneyAmount(int n) {
        int** dp = new int* [n + 2];
        for (int i = 0; i < n+2; ++i) {
            dp[i] = new int[n+2];
            memset(dp[i], 0, (n + 1)*sizeof(int));
        }
        for (int len = 2; len <= n; ++len) {
            for (int i = 1; i <= n - len + 1; ++i) {
                int min_ = INT32_MAX;
                for (int j = i; j < i + len; ++j) {
                    int tmp = max(dp[i][j - 1], dp[j + 1][i + len - 1]) + j;
                    min_ = min(min_, tmp);
                }
                dp[i][i + len - 1] = min_;
            }
        }
        return dp[1][n];
    }
};